// Copyright 2000-2024 JetBrains s.r.o. and contributors. Use of this source code is governed by the Apache 2.0 license.
package com.intellij.codeInsight.daemon.impl;

import com.intellij.codeInspection.LocalInspectionTool;
import com.intellij.codeInspection.LocalInspectionToolSession;
import com.intellij.codeInspection.ProblemsHolder;
import com.intellij.codeInspection.ex.LocalInspectionToolWrapper;
import com.intellij.injected.editor.DocumentWindow;
import com.intellij.lang.ASTNode;
import com.intellij.lang.Language;
import com.intellij.lang.annotation.Annotator;
import com.intellij.lang.annotation.HighlightSeverity;
import com.intellij.lang.injection.InjectedLanguageManager;
import com.intellij.openapi.Disposable;
import com.intellij.openapi.application.ex.ApplicationManagerEx;
import com.intellij.openapi.diagnostic.Logger;
import com.intellij.openapi.editor.Document;
import com.intellij.openapi.editor.RangeMarker;
import com.intellij.openapi.editor.colors.EditorColorsUtil;
import com.intellij.openapi.editor.ex.MarkupModelEx;
import com.intellij.openapi.editor.ex.RangeHighlighterEx;
import com.intellij.openapi.editor.impl.DocumentMarkupModel;
import com.intellij.openapi.editor.impl.SweepProcessor;
import com.intellij.openapi.editor.markup.HighlighterTargetArea;
import com.intellij.openapi.editor.markup.MarkupModel;
import com.intellij.openapi.editor.markup.TextAttributes;
import com.intellij.openapi.progress.ProgressIndicator;
import com.intellij.openapi.progress.ProgressManager;
import com.intellij.openapi.progress.util.ProgressWrapper;
import com.intellij.openapi.project.Project;
import com.intellij.openapi.util.*;
import com.intellij.openapi.util.registry.Registry;
import com.intellij.openapi.util.text.StringUtil;
import com.intellij.psi.*;
import com.intellij.psi.impl.PsiManagerEx;
import com.intellij.psi.impl.file.impl.FileManagerImpl;
import com.intellij.psi.impl.source.tree.injected.InjectedFileViewProvider;
import com.intellij.psi.impl.source.tree.injected.InjectedLanguageManagerImpl;
import com.intellij.psi.scope.PsiScopeProcessor;
import com.intellij.psi.search.GlobalSearchScope;
import com.intellij.psi.search.SearchScope;
import com.intellij.psi.util.PsiUtilCore;
import com.intellij.util.ArrayUtil;
import com.intellij.util.ExceptionUtil;
import com.intellij.util.ObjectUtils;
import com.intellij.util.PairProcessor;
import com.intellij.util.concurrency.AppExecutorUtil;
import com.intellij.util.containers.CollectionFactory;
import com.intellij.util.containers.ContainerUtil;
import it.unimi.dsi.fastutil.longs.Long2ObjectMap;
import it.unimi.dsi.fastutil.longs.Long2ObjectOpenHashMap;
import org.jetbrains.annotations.NotNull;
import org.jetbrains.annotations.Nullable;

import javax.swing.*;
import java.util.*;
import java.util.concurrent.ScheduledFuture;
import java.util.concurrent.TimeUnit;
import java.util.function.BiPredicate;
import java.util.function.Consumer;
import java.util.function.Predicate;
import java.util.stream.Collectors;

final class HighlightInfoUpdaterImpl extends HighlightInfoUpdater implements Disposable {
  private static final Logger LOG = Logger.getInstance(HighlightInfoUpdaterImpl.class);
  static boolean ASSERT_INVARIANTS; // true if some complex internal invariants must be checked on every operation
  private static final Object UNKNOWN_ID = "unknownId";
  /**
   * {@link HighlightInfo#group} which means this {@link HighlightInfo} is managed by {@link HighlightInfoUpdaterImpl},
   * i.e. its {@link HighlightInfo#group} is essentially ignored and infos are reused/deleted by {@link #psiElementVisited}
   * instead of {@link BackgroundUpdateHighlightersUtil#setHighlightersInRange} or {@link UpdateHighlightersUtil#setHighlightersInRange}
   */
  final static int MANAGED_HIGHLIGHT_INFO_GROUP = -6;

  // containing File -> tool id -> map of (visited PsiElement -> list of HighlightInfos generated by this tool while visiting that PsiElement)
  private static final Key<Map<PsiFile, Map<Object, ToolHighlights>>> VISITED_PSI_ELEMENTS = Key.create("VISITED_PSI_ELEMENTS");

  private class ToolHighlights {
    // list of HighlightInfos generated by a tool after visited this PsiElement. By convention, the list is sorted by Segment.BY_START_OFFSET_THEN_END_OFFSET
    @NotNull
    final Map<PsiElement, List<? extends HighlightInfo>> elementHighlights = CollectionFactory.createSoftMap((map, evicted) -> {
      if (evicted != null) {
        removeEvicted(map, evicted);
      }
    });
    @NotNull
    ToolLatencies latencies = new ToolLatencies(0,0,0);

    private ToolHighlights() {
      // to prevent reentrant execution of removeEvicted, we store evicted HighlightInfos in a (mutable) ArrayList under the (non-evictable) key PsiUtilCore.NULL_PSI_ELEMENT
      elementHighlights.put(PsiUtilCore.NULL_PSI_ELEMENT, new ArrayList<>());
    }
  }
  record ToolLatencies(
      long errorLatency, // latency of the first error, in nanoseconds (or 0 if none)
      long warningLatency, // latency of the first warning, in nanoseconds (or 0 if none)
      long otherLatency // latency of the first other info, in nanoseconds (or 0 if none)
  ) {
    int compareLatencies(@NotNull ToolLatencies other) {
      int o = cmp(errorLatency, other.errorLatency);
      if (o != 0) return o;
      o = cmp(warningLatency, other.warningLatency);
      if (o != 0) return o;
      o = cmp(otherLatency, other.otherLatency);
      return o;
    }
    static int cmp(long lat1, long lat2) {
      return Long.compare(lat1 == 0 ? Long.MAX_VALUE : lat1, lat2 == 0 ? Long.MAX_VALUE : lat2);
    }
  }

  HighlightInfoUpdaterImpl(Project project) {
    FileManagerImpl fileManager = (FileManagerImpl)PsiManagerEx.getInstanceEx(project).getFileManager();
    Disposer.register(this, () ->
      fileManager.forEachCachedDocument(document -> document.putUserData(VISITED_PSI_ELEMENTS, null)));
  }

  @Override
  public void dispose() {
  }

  private synchronized void removeEvicted(@NotNull Map<PsiElement, List<? extends HighlightInfo>> map, @NotNull List<? extends HighlightInfo> evicted) {
    if (LOG.isDebugEnabled()) {
      LOG.debug("removeEvicted: " + evicted+currentProgressInfo());
    }

    // all evicted HighlightInfos will be stored in this map[PsiUtilCore.NULL_PSI_ELEMENT], to be disposed later, in recycleInvalidPsiElements(), when the HighlightSession is available
    // do not use map.compute() or similar because they call .put() which invokes processQueue() which might call this method recursively which could cause SOE. This computeIfAbsent() is better because we risk at most 2-level reentrancy here
    List<HighlightInfo> storedEvicted = (List<HighlightInfo>)map.get(PsiUtilCore.NULL_PSI_ELEMENT);
    storedEvicted.addAll(evicted);
  }

  @NotNull
  private Map<Object, ToolHighlights> getData(@NotNull PsiFile psiFile) {
    PsiFile hostFile = InjectedLanguageManager.getInstance(psiFile.getProject()).getTopLevelFile(psiFile);
    Document hostDocument = hostFile.getFileDocument(); // store in the document because DocumentMarkupModel is associated with this document
    return getData(psiFile, hostDocument);
  }

  @NotNull
  private Map<Object, ToolHighlights> getData(@NotNull PsiFile psiFile, @NotNull Document hostDocument) {
    Map<PsiFile, Map<Object, ToolHighlights>> map = getOrCreateHostMap(hostDocument);
    Map<Object, ToolHighlights> result = map.get(psiFile);
    if (result == null) {
      result = map.computeIfAbsent(psiFile, __->new HashMap<>());
    }
    return result;
  }

  @NotNull
  private Map<PsiFile, Map<Object, ToolHighlights>> getOrCreateHostMap(@NotNull Document hostDocument) {
    Map<PsiFile, Map<Object, ToolHighlights>> map = hostDocument.getUserData(VISITED_PSI_ELEMENTS);
    if (map == null) {
      map = ((UserDataHolderEx)hostDocument).putUserDataIfAbsent(VISITED_PSI_ELEMENTS, CollectionFactory.createSoftMap((__, oldMap) -> {
        if (oldMap != null) {
          removeEvictedFile(oldMap);
        }
      }));
    }
    return map;
  }

  private static void invokeProcessQueueToTriggerEvictedListener(@NotNull Map<? extends PsiElement, ?> map) {
    Object v = map.remove(PsiUtilCore.NULL_PSI_FILE); // to invoke processQueue() and call evictionListener if needed
    assert null == v : v;
  }

  private synchronized void removeEvictedFile(@NotNull Map<Object, ToolHighlights> map) {
    for (ToolHighlights toolHighlights : map.values()) {
      invokeProcessQueueToTriggerEvictedListener(toolHighlights.elementHighlights);
      List<HighlightInfo> allInfos = ContainerUtil.flatten(toolHighlights.elementHighlights.values());
      removeEvicted(toolHighlights.elementHighlights, allInfos);
    }
  }

  @Override
  synchronized void removeInfosForInjectedFilesOtherThan(@NotNull PsiFile hostPsiFile,
                                                         @NotNull TextRange restrictRange,
                                                         @NotNull HighlightingSession highlightingSession,
                                                         @NotNull Collection<? extends PsiFile> liveInjectedFiles) {
    InjectedLanguageManager injectedLanguageManager = InjectedLanguageManager.getInstance(hostPsiFile.getProject());
    Document hostDocument = hostPsiFile.getFileDocument();
    Map<PsiFile, Map<Object, ToolHighlights>> hostMap = getOrCreateHostMap(hostDocument);
    hostMap.entrySet().removeIf(entry -> {
      PsiFile psiFile = entry.getKey();
      Map<Object, ToolHighlights> toolMap = entry.getValue();
      boolean shouldRemove = injectedLanguageManager.isInjectedFragment(psiFile) &&
                  !liveInjectedFiles.contains(psiFile) &&
                  restrictRange.contains(injectedLanguageManager.injectedToHost(psiFile, psiFile.getTextRange()));
      if (shouldRemove) {
        removeAllHighlighterInsideFile(psiFile, this, highlightingSession, toolMap);
        return true;
      }
      return false;
    });
  }

  // dispose all range highlighters from recycler while removing corresponding (invalid) PSI elements from the data
  synchronized void incinerateAndRemoveFromDataAtomically(@NotNull ManagedHighlighterRecycler recycler) {
    // remove highlighters which were reused or incinerated from the HighlightInfoUpdater's maps
    Collection<? extends InvalidPsi> psiElements = recycler.forAllInGarbageBin();
    if (!psiElements.isEmpty()) {
      if (LOG.isDebugEnabled()) {
        LOG.debug("incinerateAndRemoveFromDataAtomically: psiElements (" + psiElements.size() + "): " + psiElements + currentProgressInfo());
      }
    }
    removeFromDataAtomically(psiElements, recycler.myHighlightingSession);
    recycler.incinerateAndClear();
  }

  static @NotNull String currentProgressInfo() {
    ProgressIndicator indicator = ProgressManager.getGlobalProgressIndicator();
    ProgressIndicator original = ProgressWrapper.unwrap(indicator);
    return "; progress=" + (indicator == original ? "" : "wrapped:")+
           (indicator == null ? "null" + "\n" + ExceptionUtil.getThrowableText(new Throwable()) :System.identityHashCode(original) + (indicator.isCanceled() ? "X" : "V"));
  }

  // remove `psis` from `data` in one batch for all infos in the list because there can be a lot of them
  private void removeFromDataAtomically(@NotNull Collection<? extends InvalidPsi> psis, @NotNull HighlightingSession session) {
    if (psis.isEmpty()) return;
    Map<Object, ToolHighlights> data = getData(session.getPsiFile(), session.getDocument());
    Map<Object, Map<PsiElement, List<HighlightInfo>>> byPsiElement = new HashMap<>();
    for (InvalidPsi invalidPsi : psis) {
      Object toolId = invalidPsi.info().toolId;
      List<HighlightInfo> infos =
      byPsiElement.computeIfAbsent(toolId, __->new HashMap<>())
                  .computeIfAbsent(invalidPsi.psiElement(), __ -> new ArrayList<>());
      infos.add(invalidPsi.info());
    }
    for (Map.Entry<Object, Map<PsiElement, List<HighlightInfo>>> entry : byPsiElement.entrySet()) {
      Object toolId = entry.getKey();
      ToolHighlights toolHighlights = data.get(toolId);
      if (toolHighlights == null) continue;
      Map<PsiElement, List<HighlightInfo>> byPsiMap = entry.getValue();
      for (Map.Entry<PsiElement, List<HighlightInfo>> byPsiEntry : byPsiMap.entrySet()) {
        PsiElement psiElement = byPsiEntry.getKey();
        List<? extends HighlightInfo> oldInfos = ObjectUtils.notNull(toolHighlights.elementHighlights.get(psiElement), List.of());
        List<HighlightInfo> toRemove = ContainerUtil.sorted(byPsiEntry.getValue(), Segment.BY_START_OFFSET_THEN_END_OFFSET);
        List<HighlightInfo> resultInfos = new ArrayList<>();
        ContainerUtil.processSortedListsInOrder(oldInfos, toRemove, (o1, o2) -> {
          int r = Segment.BY_START_OFFSET_THEN_END_OFFSET.compare(o1, o2);
          if (r != 0) return r;
          // have to compare highlighters because we don't want to remove otherwise equal HighlightInfo except for its (recreated) highlighter
          RangeHighlighterEx h1 = o1.getHighlighter();
          RangeHighlighterEx h2 = o2.getHighlighter();
          return System.identityHashCode(h1)-System.identityHashCode(h2);
        }, true, (info, result) -> {
          if (result == ContainerUtil.MergeResult.COPIED_FROM_LIST1) {
            resultInfos.add(info);
          }
          // in other cases when the info is either from toRemove or both, skip it
        });
        toolHighlights.elementHighlights.put(psiElement, List.copyOf(resultInfos));
        if (LOG.isDebugEnabled()) {
          LOG.debug("removeFromDataAtomically: " + psiElement.getClass() + psiElement.getTextRange()+": old=" + oldInfos.size()+(oldInfos.size() == resultInfos.size() ? "; "+StringUtil.join(oldInfos, "\n   ")+"\n  " : "")
                    + "; new=" + resultInfos.size()+(oldInfos.size() == resultInfos.size() ? "; "+StringUtil.join(resultInfos, "\n   ")+"\n  "+"toRemove=("+toRemove.size()+") "+StringUtil.join(toRemove, "\n   ") : "")
                    + currentProgressInfo());
        }
      }
    }
  }

  private synchronized void recycleInvalidPsiElements(@NotNull PsiFile psiFile,
                                                      @NotNull Object requestor,
                                                      @NotNull HighlightingSession session,
                                                      @NotNull ManagedHighlighterRecycler invalidPsiRecycler,
                                                      @NotNull WhatTool toolIdPredicate) {
    TextRange compositeDocumentDirtyRange = session instanceof HighlightingSessionImpl impl ? impl.getCompositeDocumentDirtyRange() : TextRange.EMPTY_RANGE;
    collectPsiElements(psiFile, requestor, session, toolIdPredicate,
        psiElement -> psiElement == PsiUtilCore.NULL_PSI_ELEMENT/*evicted*/ || psiElement != FAKE_ELEMENT && !psiElement.isValid(), // find invalid PSI
        (info, psiElement) -> {
          if (psiElement == PsiUtilCore.NULL_PSI_ELEMENT) {
            // the psiElement for this HighlightInfo was evicted, dispose HighlightInfo
            UpdateHighlightersUtil.disposeWithFileLevelIgnoreErrors(info, session);
            return false; // remove from the list
          }
          // heuristic: when the incremental reparse support is poor, and a lot of PSI is invalidated unnecessarily on each typing,
          //  that PSI has a big chance to be recreated in that exact place later, when a (major) chunk of the file is reparsed, so we do not kill that highlighter, just recycle it to avoid annoying blinking
          // if however, that invalid PSI highlighter wasn't recycled after a short delay, kill it (runWithInvalidPsiRecycler()) to improve responsiveness to outdated infos
          if (LOG.isDebugEnabled()) {
            LOG.debug("recycleInvalidPsiElements (predicate=" + toolIdPredicate + ") " + info.getHighlighter() +
                      "; compositeDocumentDirtyRange=" + compositeDocumentDirtyRange +
                      "; toolIdPredicate=" + toolIdPredicate +
                      " for invalid " + psiElement + " from " + requestor +
                      currentProgressInfo());
          }
          invalidPsiRecycler.recycleHighlighter(psiElement, info);
          return true;
        }
    );

    if (LOG.isDebugEnabled()) {
      LOG.debug("recycleInvalidPsiElements: result predicate=" +toolIdPredicate+
                " recycler(" +invalidPsiRecycler.forAllInGarbageBin().size()+")"+
                "=\n    " + StringUtil.join(invalidPsiRecycler.forAllInGarbageBin(), "\n    ")+
                currentProgressInfo());
    }
  }

  enum WhatTool { INSPECTION, ANNOTATOR_OR_VISITOR }
  private synchronized void collectPsiElements(@NotNull PsiFile psiFile,
                                               @NotNull Object requestor,
                                               @NotNull HighlightingSession session,
                                               @NotNull WhatTool toolPredicate,
                                               @NotNull Predicate<? super PsiElement> psiElementPredicate,
                                               @NotNull PairProcessor<? super HighlightInfo, ? super PsiElement> rangeHighlighterProcessor// return true if keep in the map, false if delete
  ) {
    InjectedLanguageManager injectedLanguageManager = InjectedLanguageManager.getInstance(psiFile.getProject());
    PsiFile hostFile = injectedLanguageManager.getTopLevelFile(psiFile);
    Document hostDocument = hostFile.getFileDocument();
    Map<PsiFile, Map<Object, ToolHighlights>> hostMap = getOrCreateHostMap(hostDocument);
    List<Map<Object, ToolHighlights>> maps = new ArrayList<>();
    PsiDocumentManager documentManager = PsiDocumentManager.getInstance(hostFile.getProject());
    // for invalid files, remove all highlighters inside immediately, there's no chance they'll ever be reused
    hostMap.entrySet().removeIf(entry -> {
      PsiFile psi = entry.getKey();
      Map<Object, ToolHighlights> toolMap = entry.getValue();
      if (psi.isValid()) {
        Document document = documentManager.getDocument(psi);
        Document topLevelDocument = document instanceof DocumentWindow ? ((DocumentWindow)document).getDelegate() : document;
        if (topLevelDocument == hostDocument) {
          maps.add(toolMap);
        }
        return false;
      }
      if (psi == psiFile) {
        return false;
      }
      removeAllHighlighterInsideFile(psi, requestor, session, toolMap);
      return true;
    });


    for (Map<Object, ToolHighlights> map : maps) {
      if (map.isEmpty()) {
        continue;
      }
      for (Map.Entry<Object, ToolHighlights> toolEntry : map.entrySet()) {
        ToolHighlights toolHighlights = toolEntry.getValue();
        Object toolId = toolEntry.getKey();
        invokeProcessQueueToTriggerEvictedListener(toolHighlights.elementHighlights);


        boolean toolIdMatches = isInspectionToolId(toolId) ? toolPredicate == WhatTool.INSPECTION :
                                isAnnotatorToolId(toolId) || isHighlightVisitorToolId(toolId) ? toolPredicate == WhatTool.ANNOTATOR_OR_VISITOR :
                                false;
        if (!toolIdMatches) {
          continue;
        }
        toolHighlights.elementHighlights.entrySet().removeIf(entry -> {
          PsiElement psiElement = entry.getKey();
          ProgressManager.checkCanceled();
          if (psiElementPredicate.test(psiElement)) {
            List<? extends HighlightInfo> oldInfos = entry.getValue();
            List<HighlightInfo> newInfos = new ArrayList<>(oldInfos.size());
            for (HighlightInfo oldInfo : oldInfos) {
              if (rangeHighlighterProcessor.process(oldInfo, psiElement)) {
                newInfos.add(oldInfo);
              }
            }
            if (psiElement == PsiUtilCore.NULL_PSI_ELEMENT) {
              // for evicted infos list - after we disposed all infos, save the (empty) mutable list back, we'll need it for future evictions
              entry.setValue(newInfos);
              return false;
            }
            else if (newInfos.isEmpty()) {
              // the list is empty, remove the key (except for evicted info list)
              return true;
            }
            if (newInfos.size() != oldInfos.size()) {
              entry.setValue(List.copyOf(newInfos));
            }
          }
          return false;
        });
      }
    }
  }

  private static void removeAllHighlighterInsideFile(@NotNull PsiFile psiFile,
                                                     @NotNull Object requestor,
                                                     @NotNull HighlightingSession highlightingSession,
                                                     @NotNull Map<Object, ToolHighlights> toolMap) {
    int removed = 0;
    for (ToolHighlights highlights : toolMap.values()) {
      for (List<? extends HighlightInfo> list : highlights.elementHighlights.values()) {
        for (HighlightInfo info : list) {
          UpdateHighlightersUtil.disposeWithFileLevelIgnoreErrors(info, highlightingSession);
          removed++;
        }
      }
    }
    if (LOG.isDebugEnabled()) {
      LOG.debug("removeAllHighlighterInsideFile: removed invalid file: " + psiFile + " (" + removed + " highlighters removed); from " + requestor+currentProgressInfo());
    }
  }

  /**
   * Tool {@code toolId} has generated (maybe empty) {@code newInfos} highlights during visiting PsiElement {@code visitedPsiElement}.
   * Remove all highlights that this tool had generated earlier during visiting this psi element, and replace them with {@code newInfos}
   * Do not read below, it's very private and just for me.
   * --
   * - retrieve {@code List<HighlightInfo> oldInfos} from {@code data[toolId, psiElement]}
   * - match the oldInfos with newInfos, obtaining 3 lists:
   *  1) a list of infos from {@code oldInfos} removed from newInfos - their RHs need to be disposed
   *  2) a list of infos from {@code newInfos} absent in oldInfos - new RHs must be created for those
   *  3) a list of infos which exist in both {@code oldInfos} and {@code newInfos} - their RHs from {@code oldInfos} must be reused and stored in {@code newInfos}
   * - store {@code newInfos} with correctly updated RHs back to {@code data[toolId, psiElement]}
   * All this must be in an atomic, PCE-non-cancelable block, maintaining the following invariant: it's guaranteed that upon completion there will be
   * - no dangling RHs are in markup (dangling RH is the one not referenced from data), - to avoid duplicating RHs
   * - no removed and then recreated RHs, - to avoid blinking
   * N.B. Sometimes multiple file editors are submitted for highlighting, some of which may have the same underlying document,
   * e.g., when the editor for the file is opened along with the git log with "preview diff" for the same file.
   * In this case, it's possible that several instances of e.g., LocalInspectionPass can run in parallel,
   * thus making `psiElementVisited` potentially reentrant (i.e., it can be called with the same `toolId` from different threads concurrently),
   * so we need to guard {@link ToolHighlights} against parallel modification.
   * @param toolId one of
   *               {@code String}: the tool is a {@link LocalInspectionTool} with its {@link LocalInspectionTool#getShortName()}==toolId
   *               {@code Class<? extends Annotator>}: the tool is an {@link Annotator} of the corresponding class
   *               {@code Class<? extends HighlightVisitor>}: the tool is a {@link HighlightVisitor} of the corresponding class
   *               {@code Object: Injection background and syntax from InjectedGeneralHighlightingPass#INJECTION_BACKGROUND_ID }
   */
  @Override
  synchronized void psiElementVisited(@NotNull Object toolId,
                                      @NotNull PsiElement visitedPsiElement,
                                      @NotNull List<? extends HighlightInfo> newInfos,
                                      @NotNull Document hostDocument,
                                      @NotNull PsiFile psiFile,
                                      @NotNull Project project,
                                      @NotNull HighlightingSession session,
                                      @NotNull ManagedHighlighterRecycler invalidElementRecycler) {
    assertMarkupDataConsistent(psiFile);
    Map<Object, ToolHighlights> data = getData(psiFile, hostDocument);
    ToolHighlights toolHighlights = data.get(toolId);
    List<? extends HighlightInfo> oldInfos = ContainerUtil.notNullize(toolHighlights == null ? null : toolHighlights.elementHighlights.get(visitedPsiElement));
    if (!oldInfos.isEmpty() || !newInfos.isEmpty()) {
      // execute in non-cancelable block. It should not throw PCE anyway, but just in case
      ProgressManager.getInstance().executeNonCancelableSection(() -> {
        //assertNoDuplicates(psiFile, getInfosFromMarkup(hostDocument, project), "markup before psiElementVisited ");

        if (LOG.isDebugEnabled()) {
          //noinspection removal
          LOG.debug("psiElementVisited: " + visitedPsiElement + " in " + visitedPsiElement.getTextRange() +
                    (psiFile.getViewProvider() instanceof InjectedFileViewProvider ? " injected in " + InjectedLanguageManager.getInstance(project).injectedToHost(psiFile, psiFile.getTextRange()) : "") +
                    "; tool:" + toolId + "; infos:" + newInfos + "; oldInfos:" + oldInfos + currentProgressInfo());
        }

        ManagedHighlighterRecycler.runWithRecycler(session, recycler -> {
          for (HighlightInfo oldInfo : oldInfos) {
            RangeHighlighterEx highlighter = oldInfo.getHighlighter();
            if (highlighter != null) {
              recycler.recycleHighlighter(visitedPsiElement, oldInfo);
            }
          }
          List<? extends HighlightInfo> newInfosToStore = assignRangeHighlighters(toolId, newInfos, session, psiFile, hostDocument, invalidElementRecycler, recycler);
          ToolHighlights notNullToolHighlights = toolHighlights == null ? data.computeIfAbsent(toolId, __ -> new ToolHighlights()) : toolHighlights;
          notNullToolHighlights.elementHighlights.put(visitedPsiElement, newInfosToStore);

          //recycler.incinerateAndClear(); // do not remove from data because we just calculated new infos manually and removed the old ones, so we don't want to remove them again
          if (LOG.isDebugEnabled()) {
            LOG.debug("remap: newInfos:" + newInfosToStore + "; oldInfos: " + oldInfos+currentProgressInfo());
          }

          assertNoDuplicates(psiFile, newInfosToStore, "psiElementVisited ");
        });
      });
      //assertNoDuplicates(psiFile, getInfosFromMarkup(hostDocument, project), "markup after psiElementVisited ");
      assertMarkupDataConsistent(psiFile);
    }
  }

  private synchronized void assertNoDuplicates(@NotNull PsiFile psiFile, @NotNull List<? extends HighlightInfo> infos, @NotNull String cause) {
    if (!ASSERT_INVARIANTS) return;
    record HI(TextRange range, String desc, TextAttributes attributes){}
    List<HI> map = ContainerUtil.map(infos, h -> new HI(TextRange.create(h), h.getDescription(), h.getTextAttributes(psiFile, EditorColorsUtil.getGlobalOrDefaultColorScheme())));
    if (new HashSet<HI>(map).size() != infos.size()) {
      //int i = 0;
      // duplicates are still possible when e.g. two range highlighters (with same desc) are merged into one after the doc modifications
      // try to remove invalid PSI elements and retry the check
      List<HighlightInfo> filtered = ContainerUtil.filter(infos, info -> {
        PsiElement psiElement = findPsiElement(info, psiFile);
        return psiElement != null && psiElement.isValid();
      });
      List<HI> map2 = ContainerUtil.map(filtered, h -> new HI(TextRange.create(h), h.getDescription(), h.getTextAttributes(psiFile, EditorColorsUtil.getGlobalOrDefaultColorScheme())));
      if (new HashSet<HI>(map2).size() != filtered.size()) {
        LOG.error(cause + "Duplicates found: \n" + StringUtil.join(ContainerUtil.sorted(filtered, UpdateHighlightersUtil.BY_ACTUAL_START_OFFSET_NO_DUPS), "\n"));
      }
    }
  }

  synchronized
  private PsiElement findPsiElement(HighlightInfo info, @NotNull PsiFile psiFile) {
    Map<Object, ToolHighlights> data = getData(psiFile);
    ToolHighlights highlights = data.get(info.toolId);
    for (Map.Entry<PsiElement, List<? extends HighlightInfo>> entry : highlights.elementHighlights.entrySet()) {
      PsiElement psiElement = entry.getKey();
      if (ContainerUtil.containsIdentity(entry.getValue(), info)) {
        return psiElement;
      }
    }
    return null;
  }

  @NotNull
  static Set<HighlightInfo> getInfosFromMarkup(@NotNull Document document, @Nullable Project project) {
    if (!ASSERT_INVARIANTS) return Set.of();
    return Arrays.stream(DocumentMarkupModel.forDocument(document, project, true).getAllHighlighters())
      .map(m -> HighlightInfo.fromRangeHighlighter(m))
      .filter(Objects::nonNull)
      .collect(Collectors.toSet());
  }

  synchronized void assertMarkupDataConsistent(@NotNull PsiFile psiFile) {
    if (!ASSERT_INVARIANTS) return;
    Set<HighlightInfo> fromMarkup = getInfosFromMarkup(psiFile.getFileDocument(), psiFile.getProject());
    Set<HighlightInfo> fromData = getData(psiFile).values().stream()
      .flatMap(t -> t.elementHighlights.values().stream())
      .flatMap(l->l.stream())
      .filter(h -> h.getHighlighter() != null && h.getHighlighter().isValid()) // maybe LIP isn't started yet and its recycleInvalidPsi wasn't run
      .collect(Collectors.toSet());

    if (!fromMarkup.equals(fromData)) {
      String fromDataStr = StringUtil.join(ContainerUtil.sorted(fromData, Segment.BY_START_OFFSET_THEN_END_OFFSET), "\n");
      String fromMarkupStr = StringUtil.join(ContainerUtil.sorted(fromMarkup, Segment.BY_START_OFFSET_THEN_END_OFFSET), "\n");
      //UsefulTestCase.assertOrderedEquals(fromDataStr+"\n===\n"+fromMarkupStr+"===",fromDataStr, fromMarkupStr);
      throw new AssertionError("data inconsistent with markup: data:\n"
                                 + fromDataStr + "\n---------------markup:\n"
                                 + fromMarkupStr+"\n========="
      );
    }
  }

  // remove all highlight infos from `data` generated by tools absent in 'actualToolsRun'
  synchronized void removeHighlightsForObsoleteTools(@NotNull HighlightingSession highlightingSession,
                                                     @NotNull List<? extends PsiFile> injectedFragments,
                                                     @NotNull BiPredicate<? super Object, ? super PsiFile> keepToolIdPredicate) {
    for (PsiFile psiFile: ContainerUtil.append(injectedFragments, highlightingSession.getPsiFile())) {
      Map<Object, ToolHighlights> data = getData(psiFile, highlightingSession.getDocument());
      data.entrySet().removeIf(entry -> {
        Object toolId = entry.getKey();
        if (UNKNOWN_ID.equals(toolId)) {
          return false;
        }
        if (keepToolIdPredicate.test(toolId, psiFile)) {
          return false;
        }
        ToolHighlights toolHighlights = entry.getValue();
        for (List<? extends HighlightInfo> highlights : toolHighlights.elementHighlights.values()) {
          for (HighlightInfo info : highlights) {
            if (LOG.isTraceEnabled()) {
              LOG.trace("removeHighlightsForObsoleteTools: " + info);
            }
            UpdateHighlightersUtil.disposeWithFileLevelIgnoreErrors(info, highlightingSession);
          }
        }
        return true;
      });
    }
  }

  static boolean isInspectionToolId(Object toolId) {
    return toolId instanceof String;
  }
  static boolean isAnnotatorToolId(Object toolId) {
    return toolId instanceof Class<?> c && Annotator.class.isAssignableFrom(c);
  }
  static boolean isHighlightVisitorToolId(Object toolId) {
    return toolId instanceof Class<?> c && HighlightVisitor.class.isAssignableFrom(c);
  }
  static boolean isInjectionRelated(Object toolId) {
    return InjectedLanguageManagerImpl.isInjectionRelated(toolId);
  }

  // TODO very dirty method which throws all incrementality away, but we'd need to rewrite too many inspections to get rid of it
  synchronized void removeWarningsInsideErrors(@NotNull List<? extends PsiFile> injectedFragments,
                                               @NotNull Document hostDocument,
                                               @NotNull HighlightingSession highlightingSession) {
    ManagedHighlighterRecycler.runWithRecycler(highlightingSession, recycler -> {
      for (PsiFile psiFile: ContainerUtil.append(injectedFragments, highlightingSession.getPsiFile())) {
        Map<Object, ToolHighlights> map = getData(psiFile, hostDocument);
        if (map.isEmpty()) {
          continue;
        }
        List<? extends HighlightInfo> sorted = map.entrySet().stream()
          .filter(e -> isInspectionToolId(e.getKey())) // inspections only
          .flatMap(e -> e.getValue().elementHighlights.values().stream())
          .flatMap(l->l.stream())
          .sorted(UpdateHighlightersUtil.BY_ACTUAL_START_OFFSET_NO_DUPS)
          .toList();
        SweepProcessor.Generator<HighlightInfo> generator = processor -> ContainerUtil.process(sorted, processor);
        SeverityRegistrar severityRegistrar = SeverityRegistrar.getSeverityRegistrar(highlightingSession.getProject());
        SweepProcessor.sweep(generator, (__, info, atStart, overlappingIntervals) -> {
          if (!atStart) {
            return true;
          }
          if (info.isFileLevelAnnotation()) {
            return true;
          }

          // TODO uncomment if duplicates need to be removed automatically
          // Currently they are not, to manifest incorrectly written inspections/annotators earlier
          if (UpdateHighlightersUtil.isWarningCoveredByError(info, severityRegistrar, overlappingIntervals)/* || overlappingIntervals.contains(info)*/) {
            RangeHighlighterEx highlighter = info.getHighlighter();
            if (highlighter != null) {
              ToolHighlights elementHighlights = map.get(info.toolId);
              for (Map.Entry<PsiElement, List<? extends HighlightInfo>> elementEntry : elementHighlights.elementHighlights.entrySet()) {
                List<? extends HighlightInfo> infos = elementEntry.getValue();
                int i = infos.indexOf(info);
                if (i != -1) {
                  PsiElement psiElement = elementEntry.getKey();
                  recycler.recycleHighlighter(psiElement, info);
                  List<HighlightInfo> listMinusInfo = ContainerUtil.concat(infos.subList(0, i), infos.subList(i + 1, infos.size()));
                  if (listMinusInfo.isEmpty()) {
                    elementHighlights.elementHighlights.remove(psiElement);
                  }
                  else {
                    elementEntry.setValue(listMinusInfo);
                  }
                  break;
                }
              }
            }
          }
          return true;
        });
      }
      Collection<? extends InvalidPsi> warns = recycler.forAllInGarbageBin();
      if (LOG.isDebugEnabled() && !warns.isEmpty()) {
        LOG.debug("removeWarningsInsideErrors: found " + warns+currentProgressInfo());
      }
    });
  }

  /**
   * after inspections completed, save their latencies (from corresponding {@link InspectionRunner.InspectionContext#holder})
   * to use later in {@link com.intellij.codeInsight.daemon.impl.InspectionProfilerDataHolder#sortByLatencies(PsiFile, List, HighlightInfoUpdaterImpl)}
   */
  synchronized void saveLatencies(@NotNull PsiFile psiFile, @NotNull Map<Object, ToolLatencies> latencies) {
    if (!psiFile.getViewProvider().isPhysical()) {
      // ignore editor text fields/consoles etc.
      return;
    }
    Map<Object, ToolHighlights> map = getData(psiFile);
    if (map.isEmpty()) return;
    for (Map.Entry<Object, ToolLatencies> entry : latencies.entrySet()) {
      Object toolId = entry.getKey();
      ToolHighlights toolHighlights = map.get(toolId);
      // no point saving latencies if nothing was reported
      if (toolHighlights == null) continue;

      ToolLatencies lats = entry.getValue();
      toolHighlights.latencies = new ToolLatencies(merge(toolHighlights.latencies.errorLatency, lats.errorLatency),
                                                   merge(toolHighlights.latencies.warningLatency, lats.warningLatency),
                                                   merge(toolHighlights.latencies.otherLatency, lats.otherLatency));
    }
  }

  private static long merge(long oldL, long newL) {
    return oldL == 0 || newL == 0 ? oldL+newL : Math.min(oldL, newL);
  }

  synchronized int compareLatencies(@NotNull PsiFile psiFile, @NotNull String toolId1, @NotNull String toolId2) {
    Map<Object, ToolHighlights> map = getData(psiFile);
    if (map.isEmpty()) return 0;
    ToolHighlights toolHighlights1 = map.get(toolId1);
    ToolHighlights toolHighlights2 = map.get(toolId2);
    if (toolHighlights1 == null) {
      return toolHighlights2 == null ? 0 : 1;
    }
    if (toolHighlights2 == null) {
      return -1;
    }
    return toolHighlights1.latencies.compareLatencies(toolHighlights2.latencies);
  }

  /**
   * sort `elements` by the number of produced diagnostics:
   *  - put first the elements for which this `toolWrapper` has produced some diagnostics on previous run
   *    - in case of a tie, put elements which generated higher severity diagnostics first
   *  - followed by all other elements
   */
  @NotNull
  synchronized List<? extends PsiElement> sortByPsiElementFertility(@NotNull PsiFile psiFile,
                                                                    @NotNull LocalInspectionToolWrapper toolWrapper,
                                                                    @NotNull List<? extends PsiElement> elements) {
    String toolId = toolWrapper.getShortName();
    Map<Object, ToolHighlights> map = getData(psiFile);
    if (map.isEmpty()) return elements;
    ToolHighlights toolHighlights = map.get(toolId);
    if (toolHighlights == null) return elements;
    Map<PsiElement, List<? extends HighlightInfo>> highlights = toolHighlights.elementHighlights;
    if (highlights.isEmpty()) return elements;
    List<PsiElement> sorted = new ArrayList<>(elements);
    sorted.sort((e1, e2) -> {
      List<? extends HighlightInfo> infos1 = highlights.get(e1);
      List<? extends HighlightInfo> infos2 = highlights.get(e2);
      if ((infos1 == null) != (infos2 == null)) {
        return infos1 == null ? 1 : -1; // put fertile element first
      }
      if (infos1 == null) {
        return Integer.compare(System.identityHashCode(e1), System.identityHashCode(e2)); // for consistency
      }
      // put error-generating element first
      return maxSeverity(infos2).compareTo(maxSeverity(infos1));
    });
    return sorted;
  }

  @NotNull
  private static HighlightSeverity maxSeverity(@NotNull List<? extends HighlightInfo> infos) {
    HighlightSeverity max = HighlightSeverity.INFORMATION;
    for (HighlightInfo info : infos) {
      HighlightSeverity severity = info.getSeverity();
      if (severity.compareTo(max) > 0) max = severity;
    }
    return max;
  }

  void runWithInvalidPsiRecycler(@NotNull HighlightingSession session,
                                 @NotNull WhatTool toolIdPredicate,
                                 @NotNull Consumer<? super ManagedHighlighterRecycler> invalidPsiRecyclerConsumer) {
    ManagedHighlighterRecycler.runWithRecycler(session, invalidPsiRecycler -> {
      recycleInvalidPsiElements(session.getPsiFile(), this, session, invalidPsiRecycler, toolIdPredicate);
      ScheduledFuture<?> future = AppExecutorUtil.getAppScheduledExecutorService().schedule(() -> {
        ProgressManager.getInstance().executeProcessUnderProgress(() -> {
          // grab RA first, to avoid deadlock when InvalidPsi.toString() tries to obtain RA again from within this monitor
          ApplicationManagerEx.getApplicationEx().tryRunReadAction(() -> {
            // do not incinerate when the session is canceled because even though all RHs here need to be disposed eventually, the new restarted session might have used them to reduce flicker
            if (!session.isCanceled() && !session.getProgressIndicator().isCanceled()) {
              incinerateAndRemoveFromDataAtomically(invalidPsiRecycler);
            }
            else {
              if (LOG.isDebugEnabled()) {
                LOG.debug("runWithInvalidPsiRecycler: recycler(" + toolIdPredicate + ") abandoned because the session was canceled: " + invalidPsiRecycler+currentProgressInfo());
              }
            }
          });
        }, session.getProgressIndicator());
      }, Registry.intValue("highlighting.delay.invalid.psi.info.kill.ms"), TimeUnit.MILLISECONDS);
      try {
        invalidPsiRecyclerConsumer.accept(invalidPsiRecycler);
      }
      finally {
        future.cancel(false);
      }
    });
  }
  /**
   * We associate each {@link HighlightInfo} with the PSI element for which the inspection builder has produced that info.
   * Unfortunately, there are some crazy inspections that produce infos in their {@link LocalInspectionTool#inspectionFinished(LocalInspectionToolSession, ProblemsHolder)} method instead.
   * Which is very slow, because that highlight info won't be displayed until the entire file is visited.
   * For these infos the associated PSI element is assumed to be this {@code FAKE_ELEMENT}
   */
  static final PsiElement FAKE_ELEMENT = createFakePsiElement();

  static @NotNull PsiElement createFakePsiElement() {
    return new PsiElement() {
      @Override
      public @NotNull Project getProject() {
        throw createException();
      }

      @Override
      public @NotNull Language getLanguage() {
        throw createException();
      }

      @Override
      public PsiManager getManager() {
        throw createException();
      }

      @Override
      public PsiElement @NotNull [] getChildren() {
        return EMPTY_ARRAY;
      }

      @Override
      public PsiElement getParent() {
        return null;
      }

      @Override
      public @Nullable PsiElement getFirstChild() {
        return null;
      }

      @Override
      public @Nullable PsiElement getLastChild() {
        return null;
      }

      @Override
      public @Nullable PsiElement getNextSibling() {
        return null;
      }

      @Override
      public @Nullable PsiElement getPrevSibling() {
        return null;
      }

      @Override
      public PsiFile getContainingFile() {
        return null;
      }

      @Override
      public TextRange getTextRange() {
        return TextRange.EMPTY_RANGE;
      }

      @Override
      public int getStartOffsetInParent() {
        return -1;
      }

      @Override
      public int getTextLength() {
        return 0;
      }

      @Override
      public PsiElement findElementAt(int offset) {
        return null;
      }

      @Override
      public @Nullable PsiReference findReferenceAt(int offset) {
        return null;
      }

      @Override
      public int getTextOffset() {
        return 0;
      }

      @Override
      public String getText() {
        return "";
      }

      @Override
      public char @NotNull [] textToCharArray() {
        return ArrayUtil.EMPTY_CHAR_ARRAY;
      }

      @Override
      public PsiElement getNavigationElement() {
        return null;
      }

      @Override
      public PsiElement getOriginalElement() {
        return null;
      }

      @Override
      public boolean textMatches(@NotNull CharSequence text) {
        return false;
      }

      @Override
      public boolean textMatches(@NotNull PsiElement element) {
        return false;
      }

      @Override
      public boolean textContains(char c) {
        return false;
      }

      @Override
      public void accept(@NotNull PsiElementVisitor visitor) {

      }

      @Override
      public void acceptChildren(@NotNull PsiElementVisitor visitor) {

      }

      @Override
      public PsiElement copy() {
        return null;
      }

      @Override
      public PsiElement add(@NotNull PsiElement element) {
        throw createException();
      }

      @Override
      public PsiElement addBefore(@NotNull PsiElement element, PsiElement anchor) {
        throw createException();
      }

      @Override
      public PsiElement addAfter(@NotNull PsiElement element, PsiElement anchor) {
        throw createException();
      }

      @Override
      public void checkAdd(@NotNull PsiElement element) {
        throw createException();
      }

      @Override
      public PsiElement addRange(PsiElement first, PsiElement last) {
        throw createException();
      }

      @Override
      public PsiElement addRangeBefore(@NotNull PsiElement first, @NotNull PsiElement last, PsiElement anchor) {
        throw createException();
      }

      @Override
      public PsiElement addRangeAfter(PsiElement first, PsiElement last, PsiElement anchor) {
        throw createException();
      }

      @Override
      public void delete() {
        throw createException();
      }

      @Override
      public void checkDelete() {
        throw createException();
      }

      @Override
      public void deleteChildRange(PsiElement first, PsiElement last) {
        throw createException();
      }

      @Override
      public PsiElement replace(@NotNull PsiElement newElement) {
        throw createException();
      }

      @Override
      public boolean isValid() {
        return true;
      }

      @Override
      public boolean isWritable() {
        return false;
      }

      PsiInvalidElementAccessException createException() {
        return new PsiInvalidElementAccessException(this, toString(), null);
      }

      @Override
      public @Nullable PsiReference getReference() {
        return null;
      }

      @Override
      public PsiReference @NotNull [] getReferences() {
        return PsiReference.EMPTY_ARRAY;
      }

      @Override
      public <T> T getCopyableUserData(@NotNull Key<T> key) {
        throw createException();
      }

      @Override
      public <T> void putCopyableUserData(@NotNull Key<T> key, T value) {
        throw createException();
      }

      @Override
      public boolean processDeclarations(@NotNull PsiScopeProcessor processor,
                                         @NotNull ResolveState state,
                                         PsiElement lastParent,
                                         @NotNull PsiElement place) {
        return false;
      }

      @Override
      public PsiElement getContext() {
        return null;
      }

      @Override
      public boolean isPhysical() {
        return true;
      }

      @Override
      public @NotNull GlobalSearchScope getResolveScope() {
        throw createException();
      }

      @Override
      public @NotNull SearchScope getUseScope() {
        throw createException();
      }

      @Override
      public ASTNode getNode() {
        throw createException();
      }

      @Override
      public <T> T getUserData(@NotNull Key<T> key) {
        throw createException();
      }

      @Override
      public <T> void putUserData(@NotNull Key<T> key, T value) {
        throw createException();
      }

      @Override
      public Icon getIcon(int flags) {
        throw createException();
      }

      @Override
      public boolean isEquivalentTo(final PsiElement another) {
        return this == another;
      }

      @Override
      public String toString() {
        return "FAKE_PSI_ELEMENT";
      }
    };
  }

  /**
   * for each info in `newInfos` retrieve the RH from recycler (and then invalidElementRecycler if not found) or create new RH
   * could be reentrant, be careful to avoid leaking/blinking RHs
   */
  @NotNull
  private List<? extends HighlightInfo> assignRangeHighlighters(@NotNull Object toolId,
                                                                @NotNull List<? extends HighlightInfo> newInfos,
                                                                @NotNull HighlightingSession session,
                                                                @NotNull PsiFile psiFile,
                                                                @NotNull Document hostDocument,
                                                                @NotNull ManagedHighlighterRecycler invalidElementRecycler,
                                                                @NotNull ManagedHighlighterRecycler recycler) {
    MarkupModelEx markup = (MarkupModelEx)DocumentMarkupModel.forDocument(hostDocument, session.getProject(), true);

    SeverityRegistrar severityRegistrar = SeverityRegistrar.getSeverityRegistrar(session.getProject());
    Long2ObjectMap<RangeMarker> range2markerCache = new Long2ObjectOpenHashMap<>(10);
    List<HighlightInfo> newInfosToStore = null;
    // infos which highlighters are recycled from `invalidElementRecycler` and which need to be removed from `data` to avoid its highlighter to be registered in two places
    // this list must be sorted by Segment.BY_START_OFFSET_THEN_END_OFFSET
    List<InvalidPsi> recycledInvalidPsiHighlightersToBeRemovedFromData = new ArrayList<>(newInfos.size());
    List<? extends HighlightInfo> sorted = ContainerUtil.sorted(newInfos, Segment.BY_START_OFFSET_THEN_END_OFFSET);
    for (int i = 0; i < sorted.size(); i++) {
      HighlightInfo newInfo = sorted.get(i);
      boolean isFileLevel = newInfo.isFileLevelAnnotation();
      long finalInfoRange = isFileLevel
                            ? TextRangeScalarUtil.toScalarRange(0, psiFile.getTextLength())
                            : BackgroundUpdateHighlightersUtil.getRangeToCreateHighlighter(newInfo, hostDocument);
      if (finalInfoRange == -1) {
        if (newInfosToStore == null) newInfosToStore = new ArrayList<>(sorted.subList(0, i));
        continue;
      }
      if (newInfosToStore != null) {
        newInfosToStore.add(newInfo);
      }
      int layer = isFileLevel ? DaemonCodeAnalyzerEx.FILE_LEVEL_FAKE_LAYER : UpdateHighlightersUtil.getLayer(newInfo, severityRegistrar);
      int infoStartOffset = TextRangeScalarUtil.startOffset(finalInfoRange);
      int infoEndOffset = TextRangeScalarUtil.endOffset(finalInfoRange);

      InvalidPsi recycled = recycler.pickupHighlighterFromGarbageBin(infoStartOffset, infoEndOffset, layer);
      String from = "recycler";
      if (recycled == null) {
        recycled = invalidElementRecycler.pickupHighlighterFromGarbageBin(infoStartOffset, infoEndOffset, layer);
        if (recycled != null) {
          recycledInvalidPsiHighlightersToBeRemovedFromData.add(recycled);
        }
        from = "invalidElementRecycler";
      }
      if (recycled != null) {
        if (LOG.isDebugEnabled()) {
          LOG.debug("assignRangeHighlighters: pickedup " + recycled + " from " + from+currentProgressInfo());
        }
      }
      changeRangeHighlighterAttributes(session, psiFile, markup, newInfo, range2markerCache, finalInfoRange, recycled, isFileLevel, infoStartOffset, infoEndOffset, layer);
    }
    removeFromDataAtomically(recycledInvalidPsiHighlightersToBeRemovedFromData, session);

    // this list must be sorted by Segment.BY_START_OFFSET_THEN_END_OFFSET
    List<HighlightInfo> result = List.copyOf(newInfosToStore == null ? sorted : newInfosToStore);
    for (int i = 0; i < result.size(); i++) {
      HighlightInfo info = result.get(i);
      assert info.getHighlighter() != null : info;
      assert info.getHighlighter().isValid() : info;
      assert HighlightInfo.fromRangeHighlighter(info.getHighlighter()) == info : "from RH: "+HighlightInfo.fromRangeHighlighter(info.getHighlighter())+"; but expected: "+info;
      if (i>0) {
        assert Segment.BY_START_OFFSET_THEN_END_OFFSET.compare(result.get(i-1), result.get(i)) <= 0 : "assignRangeHighlighters returned unsorted list: "+result;
      }
    }
    return result;
  }

  private static void changeRangeHighlighterAttributes(@NotNull HighlightingSession session,
                                                       @NotNull PsiFile psiFile,
                                                       @NotNull MarkupModelEx markup,
                                                       @NotNull HighlightInfo newInfo,
                                                       @NotNull Long2ObjectMap<RangeMarker> range2markerCache,
                                                       long finalInfoRange,
                                                       @Nullable InvalidPsi recycled,
                                                       boolean isFileLevel,
                                                       int infoStartOffset,
                                                       int infoEndOffset,
                                                       int layer) {
    TextAttributes infoAttributes = newInfo.getTextAttributes(psiFile, session.getColorsScheme());
    com.intellij.util.Consumer<RangeHighlighterEx> changeAttributes = finalHighlighter -> {
      BackgroundUpdateHighlightersUtil.changeAttributes(finalHighlighter, newInfo, session.getColorsScheme(), psiFile, infoAttributes);

      range2markerCache.put(finalInfoRange, finalHighlighter);
      newInfo.updateQuickFixFields(session.getDocument(), range2markerCache, finalInfoRange);
    };
    if (LOG.isDebugEnabled()) {
      LOG.debug("remap: create " + (recycled == null ? "(new RH)" : "(recycled)") + newInfo + currentProgressInfo());
    }
    if (recycled == null) {
      // create new
      if (isFileLevel) {
        RangeHighlighterEx highlighter = createOrReuseFakeFileLevelHighlighter(MANAGED_HIGHLIGHT_INFO_GROUP, newInfo, null, markup);
        ((HighlightingSessionImpl)session).addFileLevelHighlight(newInfo, highlighter);
      }
      else {
        //assertNoInfoInMarkup(newInfo, markup, recycler, invalidElementRecycler);
        markup.addRangeHighlighterAndChangeAttributes(null, infoStartOffset, infoEndOffset, layer,
                                                      HighlighterTargetArea.EXACT_RANGE, false,
                                                      changeAttributes);
      }
    }
    else {
      // recycle
      HighlightInfo info = recycled.info();
      RangeHighlighterEx highlighter = info.getHighlighter();
      if (isFileLevel) {
        RangeHighlighterEx highlighterToUse =
          createOrReuseFakeFileLevelHighlighter(MANAGED_HIGHLIGHT_INFO_GROUP, newInfo, highlighter, markup);
        ((HighlightingSessionImpl)session).replaceFileLevelHighlight(info, newInfo, highlighterToUse);
      }
      else {
        markup.changeAttributesInBatch(highlighter, changeAttributes);
      }
      assert info.getGroup() == HighlightInfoUpdaterImpl.MANAGED_HIGHLIGHT_INFO_GROUP: info;
    }
  }

  @NotNull
  static RangeHighlighterEx createOrReuseFakeFileLevelHighlighter(int group, @NotNull HighlightInfo info, @Nullable RangeHighlighterEx toReuse, @NotNull MarkupModel markupModel) {
    Document document = markupModel.getDocument();
    RangeHighlighterEx highlighter = toReuse != null && toReuse.isValid() ? toReuse
             : (RangeHighlighterEx)markupModel.addRangeHighlighter(0, document.getTextLength(), DaemonCodeAnalyzerEx.FILE_LEVEL_FAKE_LAYER, null, HighlighterTargetArea.EXACT_RANGE);
    highlighter.setGreedyToLeft(true);
    highlighter.setGreedyToRight(true);
    highlighter.setErrorStripeTooltip(info);
    // for the condition `existing.equalsByActualOffset(info)` above work correctly,
    // create a fake whole-file highlighter which will track the document size changes
    // and which will make possible to calculate correct `info.getActualEndOffset()`
    info.setHighlighter(highlighter);
    info.setGroup(group);
    return highlighter;
  }

  // psierrorelement reparse
  private static void assertNoInfoInMarkup(@NotNull HighlightInfo info, @NotNull MarkupModelEx markup, @NotNull ManagedHighlighterRecycler recycler, @NotNull ManagedHighlighterRecycler invalidPsiRecycler) {
    if (!ASSERT_INVARIANTS) return;
    if (ContainerUtil.mapNotNull(markup.getAllHighlighters(), m-> HighlightInfo.fromRangeHighlighter(m)).contains(info)
      && !ContainerUtil.mapNotNull(recycler.forAllInGarbageBin(), i->i.info()).contains(info)
      && !ContainerUtil.mapNotNull(invalidPsiRecycler.forAllInGarbageBin(), i->i.info()).contains(info)) {
      throw new AssertionError("Info " + info + " found in markup among "+
                               "\n   "+StringUtil.join(ContainerUtil.mapNotNull(markup.getAllHighlighters(), m-> HighlightInfo.fromRangeHighlighter(m)), Object::toString,"\n   ")+
                               "   --, even though these recyclers do not contain it:\n "+recycler.forAllInGarbageBin()+";\n "+invalidPsiRecycler.forAllInGarbageBin());
    }
  }
}
